МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ Національний університет «Львівська політехніка» Кафедра САПР Звіт до Лабораторної роботи №2 на тему: СКІНЧЕННІ АВТОМАТИ з курсу: «Лінгвістичне забезпечення САПР»  1. МЕТА РОБОТИ Навчитися моделювати роботу розпізнавача за допомогою скінченного автомата. 2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ В основі побудові компіляторів лежить теорія автоматів. Автомат – це нереально існуючий пристрій, а деяка математична модель, властивості і поведінку якої можна вивчити і яку можна імітувати на реальній ЕОМ. Скінченний автомат – це найпростіша з моделей теорії автоматів. Скінченним називається автомат, у якому множина внутрішніх станів і множина вхідних значень є скінченними множинами. Скінченний розпізнавач – це модель пристрою із скінченним числом станів, які відрізняють правильно утворенні ланцюжки символів від неправильних (недопустимих). Вхідна стрічка – це послідовність комірок, кожна комірка містить тільки один символ із скінченного вхідного алфавіту. Крайню ліву і крайню праву комірки можуть займати кінцеві маркери. Вхідна головка у кожний момент часу читає одну вхідну комірку. Пам'ять розпізнавача – це будь-яке сховище інформації або даних. Оскільки алфавіт скінченний, то об’єм пам’яті скінченний. Керуючий пристрій є ядром розпізнавача. Це програма, яка керує роботою (поведінкою) розпізнавача. Керуючий пристрій – це скінченна множина станів разом з відображенням, яке описує як змінюється стани відповідно до поточного вхідного символу та інформацією, добутою із пам’яті. Роботу розпізнавача можна відобразити в термінах його конфігурації: 1. Стан керуючого пристрою; 2. Вміст вхідної стрічки і положення вхідної головки; 3. Вміст пам’яті; Конфігурація є початковою, якщо керуючий пристрій знаходиться у заданому початковому стані, вхідна головка може читати крайній лівий символ у стрічці і пам'ять має наперед установленний вміст. Конфігурація є кінцевою, якщо керуючий пристрій знаходиться в одному з наперед визначених множиною кінцевих станів, а вхідна головка може читати правий кінцевий маркер, або вразі його відсутності, вона зійшла з правого кінця вхідної стрічки. Формально скінченний розпізнавач визначається за п’ятьма характеристиками: 1. Скінченною множиною станів
; 2. Скінченним вхідним алфавітом
; 3. Множиною переходів
, які відображають поведінку керуючого пристрою; 4. Початковим станом
; 5. Множиною кінцевих станів
. Тобто скінченний автомат
описується як
. ПРИКЛАД ПОБУДОВИ СКІНЧЕННОГО АВТОМАТА Прикладом скінченного автомата може контролер непарності «1» в ланцюжку символів, що складається з нулів і одиниць. Скінченний автомат буде допускати усі ланцюжки, які містять непарну кількість «1» і відкидати ті з них, які містять парну кількість «1». Вхідним алфавітом
такого автомата буде множина {0, 1}. Множина станів
буде складатись із двох станів ПАР і НЕПАР. Початковим станом
буде стан ПАР. При читанні наступного вхідного символу стан автомата змінюється. Новий його стан залежить від вхідного символу і поточного символу. Функція переходів
буде мати такий вигляд:
(ПАР, 0)=ПАР
(ПАР, 1)=НЕПАР
(НЕПАР, 0)=НЕПАР
(НЕПАР, 1)=ПАР Кінцевий (допускаючим) станом
є НЕПАР. Ланцюжок 1101 допускається автоматом, оскільки останнім є допускаючий стан НЕПАР. Іншою є ситуація при обробці ланцюжка 101, він відкидається, оскільки його кінцевим станом є недопустимий стан ПАР. Один із зручних методів подання скінченного автомата є таблиця переходів. Правила побудови таблиці такі: 1. Стовпці помічено символами вхідного алфавіту. 2. Рядки помічено символами станів. 3. Елементи таблиці є символами нових станів, які визначаються вхідним символом і попереднім станом. 4. Перший рядок помічено символом початкового стану. 5. Рядки, які відповідають допускаючим станам, помічені справа одиницями: рядки, які відкидаються автоматом, помічаються справа нулями. Для нашого автомата таблиця переходів показана на рис. 1. Крім табличного подання, скінченний автомат можна подати діаграмою (або графом) переход...